In conventional databases, an incoming query is typically received and manipulated by a database front end prior to being submitted to a query processor for optimization and execution. Generally, the front end uses the incoming query to generate a query plan for executing the query at the query processor. Generating an execution plan is a multi-stage process. For example, SQL Server™ from Microsoft Corp. of Redmond, Wash., is a relational database in which an execution plan may be generated as follows. First, the query may be parsed to yield an abstract syntax tree. The abstract syntax tree may then be transformed into a unified tree structure in which nodes represent abstract operations to be performed on the query. An algebrizer may then be employed to convert the unified tree operations into relational algebraic expressions in a log-op tree. The log-op tree is the resulting query plan which is submitted to the query processor for optimization and execution.
A recent development with respect to databases is that, in addition to supporting traditional relational data, the databases also support extensible markup language (XML) data. For example, SQL Server enables data to be defined using an XML data type. Columns with such an XML data type can be created in a data table, and XML variables and parameters can be declared. Such XML data can be searched, retrieved, and updated. Specifically, a query may include an XML expression written in an XML based query language such as XQuery and XSLT.
A limitation of conventional databases is that the existing method of generating a query plan set forth above is inadequate for queries that include such an XML expression. Specifically, the existing relational operations are inadequate for XML expressions that include document order and hierarchical ordering of data. Furthermore, existing algebrizers are inadequate to convert XML operations into relational algebra operations. Furthermore, existing relational algebra operations are inadequate to describe XML operations.
Thus, there is a need in the art for systems and methods for compiling an XML based query. The present invention satisfies these needs.